package com.jhy.review.day07;

/**
 * 局部最小值（0<1,n-1<n-2 i<i+1 && i<i-1   所以0和n-1和i都是局部最小)
 * 在一个数组当中，这个arr无序，任意两个相邻的数一定不相等。
 * 下面求一个局部最小的值 只需要一个就行
 * 不一定有序就二分
 * 2022年8月31日20:56:29
 */
public class FindOneLessValueIndex {

    public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1; // no exist
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
//        二分方法求局部最小值
//        临界条件
        while (left < right) {
//            求出mid的值
            mid = left + ((right-left)>>1);
//            两个数一定不相等 所以我们不用考虑相等问题
            if(arr[mid] > arr[mid-1]){
                right = mid-1;
            }else  if(arr[mid] > arr[mid+1]){
                left = mid+1;
            }else {
                return mid;
            }
        }
        /*
        *这里放回left和right是一样的
        * */
        return right;
    }

    public static void printArray(int[] arr) {
//        i不等于才会继续执行
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = { 6, 5, 3, 4, 6, 7, 8 };
        printArray(arr);
        int index = getLessIndex(arr);
        System.out.println("index: " + index + ", value: " + arr[index]);

    }
}
